home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.mactech.com 2010
/
ftp.mactech.com.tar
/
ftp.mactech.com
/
challenge
/
12.01-Jan96
/
12.01ChallengeText.sit.hqx
/
12.01 Challenge Text
next >
Wrap
Text File
|
1995-12-14
|
5KB
|
102 lines
Sliding Tiles
You have all probably seen small versions of the puzzle that is the basis for
this month’s Challenge: a 4-by-4 grid of interlocking tiles, with one empty tile
among the 16 cells allowing the puzzle to be scrambled by sliding adjacent cells
into the empty location. This month the Challenge is to write code that will
unscramble a larger version of the Sliding Tiles puzzle.
The prototype for the code you should write is:
typedef Boolean /*legalMove*/ (*MoveProc)(
/* Callback procedure to move tile at */
long tileToMoveRow, /* these coordinates into the location */
long tileToMoveCol /* of adjacent empty tile */
);
void SolveTiles(
long *tiles, /* pointer to array of tiles where */
long numRows, /* tile (row,col) is at */
long numCols, /* *(tiles + row*numCols + col) */
MoveProc MakeMove /* Callback procedure to move a tile */
);
You will be given a pointer tiles into an array of tile values, the number of
rows and columns in the puzzle (numRows and numCols, respectively), and the
address of a callback procedure MakeMove used to tell my test code about the
moves you make to solve the puzzle. The tiles array will be initialized with the
values 0..numRows*numCols-1, in an order scrambled by the calling routine. The
value 0 represents the empty tile.
Your code should make a sequence of calls to MakeMove and return when the puzzle
is solved. Each MakeMove call exchanges the empty tile with the indicated
adjacent tile. The puzzle is solved when you have moved each tile into its
proper location: moving the tile with value i into location tiles[i] (i.e.,
row=i/numCols and col=i%numCols).
The callback routine will be something like the code provided below:
static long gNumRows,gNumCols; /* initialized by test code */
static long gEmptyRow,gEmptyCol; /* initialized by test code */
static long *gTiles; /* initialized by test code */
#define TileValue(tiles,row,col) *(tiles+(row)*gNumCols+(col))
#define OutOfRange(val,num) (((val)<0) || ((val)>=(num)))
static Boolean MakeMove(long tileToMoveRow,long tileToMoveCol)
{
long diff;
if (OutOfRange(tileToMoveRow,gNumRows)) return false;
if (OutOfRange(tileToMoveCol,gNumCols)) return false;
if (tileToMoveRow == gEmptyRow) {
diff = tileToMoveCol - gEmptyCol;
} else if (tileToMoveCol == gEmptyCol) {
diff = tileToMoveRow - gEmptyRow;
} else {
return false;
}
if ((diff != -1) && (diff != 1)) return false;
TileValue(gTiles,gEmptyRow,gEmptyCol) =
TileValue(gTiles,tileToMoveRow,tileToMoveCol);
gEmptyRow = tileToMoveRow;
gEmptyCol = tileToMoveCol;
TileValue(gTiles,gEmptyRow,gEmptyCol) = 0;
}
As an example, given the initial conditions:
long tiles[] = {1,4,0,3,5,2};
SolveTiles(tiles,2,3,MakeMove);
… you could generate the following moves:
MakeMove(1,2);
MakeMove(1,1);
MakeMove(0,1);
MakeMove(0,0);
… to transform the puzzle like this:
1 4 0 ==> 1 4 2 ==> 1 4 2 ==> 1 0 2 ==> 0 1 2
3 5 2 3 5 0 3 0 5 3 4 5 3 4 5
It turns out that half of the possible permutations of the values
0..numRows*numCols-1 are “illegal” in that they cannot be reached from the
“solved” state. The calling routine will provide a legal starting state – you
don’t have to worry about the puzzle being unsolvable.
The number of moves you make to solve the puzzle is not an explicit criterion in
determining the winner, but the winner will be determined by total execution
time, including the time used by the callback routine, as we did in the Master
MindReader challenge a few months back. Note that you are not permitted to
optimize the callback routine – its purpose is to provide a fixed time penalty
for each move your solution routine makes.
This will be a native PowerPC Challenge, scored using the Symantec 8.0.3
compiler. Good luck. Email me with any questions, or – better yet – join the
Programmer’s Challenge Mailing List …
Mailing List Reminder
Many Challenge readers have already joined the Programmer’s Challenge Mailing
List announced last month. The list is being used to distribute the latest
Challenge, provide answers to questions about the current Challenge, and discuss
suggestions for future Challenges. The Challenge problem is posted to the list
sometime between the 20th and the 25th of the month.
To subscribe to the list, send a message to autoshare@mactech.com with the
SUBJECT line “sub challenge YourName”, substituting your real name for YourName.
To unsubscribe from the list, send a message to autoshare@mactech.com with the
SUBJECT line “unsub challenge”.